// 设计链表
public class DesignLinkList {
  public static void main(String[] args) {
    System.out.println("\nHello World");
  }

}
// #region
// class MyLinkedList {
// class ListNode {
// int val;// 节点的值
// ListNode next;// 下一个节点

// // 节点的构造函数
// ListNode(int val) {
// this.val = val;
// }

// }

// private int size;// size存储链表的个数
// private ListNode head;// 注意这里记录的是虚拟头节点

// // 初始化链表
// public MyLinkedList() {
// this.size = 0;
// this.head = new ListNode(0);
// }

// // 获取第index的节点的数值，注意这里的index是从0开始的，第0个节点就是虚拟头节点
// public int get(int index) {
// // 如果index非法，返回-1
// if (index < 0 || index >= size) {
// return -1;
// }
// ListNode cur = head;
// // 第0个节点是虚拟头节点，所以查找index + 1个节点
// for (int i = 0; i <= index; i++) {
// cur = cur.next;
// }
// return cur.val;
// }

// public void addAtHead(int val) {
// ListNode newNode = new ListNode(val);
// newNode.next = head.next;
// head.next = newNode;
// size++;

// /**
// * 将新节点插入到头节点之前
// * 需要注意的是：
// * 先将新节点的next指向头节点的next，再将头节点的next指向新节点
// * 如果是先将头节点的next指向新节点的话，那么就找不到原先头节点next指向的节点，就会导致新节点无法指向下一个节点
// */
// }

// public void addAtTail(int val) {
// ListNode newNode = new ListNode(val);
// ListNode cur = head;
// while (cur.next != null) {
// cur = cur.next;
// }
// cur.next = newNode;
// size++;
// /**
// * 将新节点插入到尾部
// * 循环链表，当前节点的下一节点如果指向null的时候，cur节点就是最后一个节点
// * 这时就可以将cur.next指向新节点
// */
// }

// public void addAtIndex(int index, int val) {
// // 判断是否超出范围
// if (index < 0 || index > size) {
// return;
// }

// // 找到要插入节点的前节点
// ListNode pre = head;
// for (int i = 0; i < index; i++) {
// pre = pre.next;
// }

// ListNode newNode = new ListNode(val);
// newNode.next = pre.next;
// pre.next = newNode;
// size++;

// /**
// * 在第index个节点之前插入一个新节点
// * 如果index大于链表的长度，则返回空
// * 如果index等于链表的长度，则说明是插入的新节点为链表的尾节点
// * 如果index为0的话，那么插入的新节点就是链表的头节点
// */
// }

// public void deleteAtIndex(int index) {
// if (index < 0 || index >= size) {
// return;
// }
// ListNode pre = head;
// for (int i = 0; i < index; i++) {
// pre = pre.next;
// }
// pre.next = pre.next.next;
// size--;
// }
// }
// #endregion

class MyLinkedList {
  class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
      this.val = val;
    }
  }

  private int size;
  private ListNode head;

  // 初始化链表
  public MyLinkedList() {
    this.size = 0;
    this.head = new ListNode(0);
  }

  // 链表的索引是从0开始的！！
  // 获取第index个节点的值
  public int get(int index) {
    if (index < 0 || index >= size) {
      return -1;
    }
    ListNode cur = head;
    for (int i = 0; i <= index; i++) {
      cur = cur.next;
    }

    return cur.val;
  }

  // 添加新节点到链表的头部 === 在索引为0的元素前添加
  public void addAtHead(int val) {
    ListNode newNode = new ListNode(val);
    newNode.next = head.next;
    head.next = newNode;
    size++;
  }

  // 将新节点到链表的尾部 === 在size - 1的索引后面添加元素
  public void addAtTail(int val) {
    ListNode newNode = new ListNode(val);
    ListNode cur = head;
    for (int i = 0; i < size; i++) {
      cur = cur.next;
    }
    cur.next = newNode;
    size++;
  }

  // 将新节点插入到第i个节点之前
  public void addAtIndex(int index, int val) {
    if (index < 0 || index > size) {
      return;
    }
    ListNode cur = head;

    for (int i = 0; i < index; i++) {
      cur = cur.next;
    }
    ListNode newNode = new ListNode(val);

    newNode.next = cur.next;
    cur.next = newNode;
    size++;
  }

  // 删除第i个节点
  public void deleteAtIndex(int index) {
    if (index < 0 || index >= size) {
      return;
    }
    ListNode pre = head;
    for (int i = 0; i < index; i++) {
      pre = pre.next;
    }
    pre.next = pre.next.next;
    size--;
  }

}